public class Sort {

    /**
     * 冒泡排序：
     * 时间复杂度：【讨论 没有优化的情况下，也就是 没有下方的 boolean元素和-i操作】
     *           O(N^2)
     *           优化以后 可能会达到O(N)
     * 空间复杂度：O(1)
     * 稳定性：稳定的排序
     * @param array
     */
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length; i++) {
            //加入判断进行优化
            boolean flg = true;
            // j < array.length -1 - i 这里的 -i 也是一种优化
            for (int j = 0; j < array.length -1 - i; j++) {
                if(array[j] > array[j + 1]) {
                    swap(array,j,j + 1);
                    flg = false;
                }
            }
            if(flg) {
                break;
            }
        }
    }

    public static void swap(int[] array,int i,int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }

}
